<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      var countBits = function (n) {
        // 方法一：暴力法（）---时间：O（n*(2m)）（m是二进制数组的长度）---空间：O（n+m）（两个数组长度）
        // const arr = [];
        // for (let i = 0; i <= n; i++) {
        //   const strArr = i.toString(2).split("");
        //   let count = 0
        //   for (let j = 0; j < strArr.length; j++) {
        //     if (strArr[j] === '1') {
        //       count++;
        //     }
        //   }
        //   arr[i] = count;
        // }
        // return arr

        // 方法二：Brian Kernighan 算法---时间：O（n*(logn)）（）---空间：O（1）（官方又没有计算数组长度进去）
        const arr = [];
        let count = 0;
        for (let i = 0; i <= n; i++) {
          count = 0
          arr[i] = getCount(i);
        }
        function getCount(i) {
          while (i > 0) {
            i = i & (i - 1);
            count++;
          }
          return count;
        }
        return arr;

        // 方法三：使用奇数偶数的规律（https://leetcode.cn/problems/counting-bits/solutions/7882/hen-qing-xi-de-si-lu-by-duadua/?orderBy=most_votes）
        // ---时间：O（n）（）---空间：O（n）（数组长度）
        // const arr = [];
        // arr[0] = 0;
        // for (let i = 0; i <= n; i++) {
        //   // if (i % 2 === 1) {
        //   //   arr[i] = arr[i - 1] + 1;
        //   // } else {
        //   //   arr[i] = arr[i / 2];
        //   // }

        //   // 采用位运算优化
        //   arr[i] = arr[i >> 1] + (i & 1);
        // }
        // return arr;
      };
      console.log(countBits(2));
      console.log(countBits(5));
    </script>
  </body>
</html>
